package com.LeeCode;

import java.util.Arrays;

/**
 * 可移除字符的最大数目
 */

public class Code1898 {
    public static void main(String[] args) {
        String s = "abcab", p = "abc";
        int[] removable = {0, 1, 2, 3, 4};
        System.out.println(new Code1898().maximumRemovals(s, p, removable));
    }

    public int maximumRemovals(String s, String p, int[] removable) {
        char[] charS = s.toCharArray(), charP = p.toCharArray();
        boolean[] remove = new boolean[charS.length];

        int left = 0, right = removable.length + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (check(charS, charP, removable, remove, mid))
                left = mid;
            else
                right = mid;
        }
        return left;
    }

    private boolean check(char[] s, char[] p, int[] removable, boolean[] remove, int k) {
        Arrays.fill(remove, false);
        for (int i = 0; i < k; i++) {
            remove[removable[i]] = true;
        }
        int index = 0, len = p.length;
        for (int i = 0; i < s.length; i++) {
            if (!remove[i] && s[i] == p[index]) {
                index++;
            }
            if (index == len)
                return true;
        }
        return false;
    }

}
